//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组 
// 👍 1401 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.*;

public class LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
        solution.largestRectangleArea(new int[]{2,4});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private LinkedList<Integer> stack = new LinkedList<>();
        private int[] indexs;
        private LinkedList<Integer> stackReverse = new LinkedList<>();
        private int[] indexsReverse;

        public int largestRectangleArea(int[] heights) {
            ArrayList<Integer> heightsArray = new ArrayList<>();
            heightsArray.add(-1);
            for (int i = 0; i <heights.length ; i++) {
                heightsArray.add(heights[i]);
            }
            heightsArray.add(-1);

            indexs = new int[heights.length+2];
            indexsReverse = new int[heights.length+2];

            // 获取从左到右和从右到左的单调栈
            singleStack(heightsArray);
            singleStackReverse(heightsArray);

            int maxHeights = 0;

            for (int i = 1; i <heightsArray.size()-1 ; i++) {
                maxHeights = Math.max(maxHeights,(indexs[i]-indexsReverse[i]-1)* heightsArray.get(i));
            }
            return maxHeights;
        }

        public void singleStack(ArrayList<Integer> nums) {
            for (int i=0;i<nums.size();i++){
                while (!stack.isEmpty() && nums.get(stack.getLast()) > nums.get(i)){
                    indexs[stack.pollLast()]=i;
                }
                stack.addLast(i);
            }
        }
        public void singleStackReverse(ArrayList<Integer>  nums) {
            for (int i=nums.size()-1;i>=0;i--){
                while (!stackReverse.isEmpty() && nums.get(stackReverse.getLast()) > nums.get(i)){
                    indexsReverse[stackReverse.pollLast()]=i;
                }
                stackReverse.addLast(i);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}